package com.ljy.my_study.leetcode.非递减数列;

public class TestMain {

//    给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
//
//    我们是这样定义一个非递减数列的： 对于数组中所有的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
//
//             
//
//    示例 1:
//
//    输入: nums = [4,2,3]
//    输出: true
//    解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
//    示例 2:
//
//    输入: nums = [4,2,1]
//    输出: false
//    解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
//             
//
//    说明：
//
//            1 <= n <= 10 ^ 4
//            - 10 ^ 5 <= nums[i] <= 10 ^ 5
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/non-decreasing-array
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        TestMain testMain=new TestMain();
        System.out.println(testMain.checkPossibility(new int[]{3,4,2,3}));
        System.out.println(testMain.checkPossibility(new int[]{1,3,4,2,3}));
        System.out.println(testMain.checkPossibility(new int[]{4,2,1}));
        System.out.println(testMain.checkPossibility(new int[]{3,4,4,5,1,1}));
    }

    public boolean checkPossibility(int[] nums) {

        int changeIndex=-1;
        int changeNum=-1;
        for(int i=0;i<nums.length-1;i++){
            if(nums[i+1]<nums[i]){
                if(changeNum==-1){
                    //修改i的值
                    if(i==0||(nums[i-1]<=nums[i+1])){
                        changeNum=nums[i];
                        nums[i]=nums[i+1];
                        changeIndex=i;
                    }else{
                        //修改i+1的值
                        changeNum=nums[i+1];
                        nums[i+1]=nums[i];
                        changeIndex=i+1;
                    }
                }else{
                    nums[changeIndex]=changeNum;
                    return false;
                }
            }
        }
        if(changeIndex!=-1){
            nums[changeIndex]=changeNum;
        }
        return true;
    }
}
